This invention relates to the residue number system (RNS) and more particularly to an improved method of performing modulo addition that is particularly useful in apparatus for converting residue number signals to binary number signals.
It is becoming increasingly popular to design electrical equipment such as filters, CODECS and echo cancellers to perform necessary processing functions in a digital manner in order to obtain the advantages of high reliability and reproducibility of results. This requires converting an analog input signal to a digital signal, performing the necessary processing operations on the digital signal in a digital manner, and then translating the processed digital signal back into an associated analog output signal. In a digital filtering operation, for example, a series of multiplications and a long summation of product terms may be required. Since there are carries involved with basic arithmetic operations such as multiplication and addition in weighted number systems such as the decimal and binary (base 10 and base 2) number systems, time is required to accommodate all of the necessary carry operations. By way of example, there is a single carry from the units column to the 10's column when adding the numbers 9 and 5 to get the number 14 in the base 10 number system. This also applies to multiplication. And where 2 each 16 digit numbers are multiplied together to obtain a 32 digit number, it may be necessary to propagate a carry from the least significant digit in the units column all the way up to the last digit that corresponds to the most significant digit. This can be very time consuming. One technique for overcoming this time limitation that is called pipelining involves generation, in the same time, of different future product (or addition) terms corresponding to different bits and delaying them accordingly, so that all bits of a result will appear on outputs at the same time. This normally requires considerable hardware which can be costly in terms of both economics and real estate in an integrated circuit structure. Another technique for overcoming this time limitation is to perform such operations as multiplication and addition in a non-weighted number system which is called the residue number system (RNS). A residue signal processor has advantage over a conventional binary-digital processor in that results are exact, a smaller amount of hardware is required, shallower pipelining is possible, operation time may be decreased, and no carries are involved.
During recent years there has been considerable interest in and development of techniques for performing digital computing and digital signal processing with hardware based on the RNS. This interest stems at least partially from the fact that operations can be performed quickly in the RNS because of the separability of operations on each RNS digit and the elimination of carries. Residue signal processor means must sample analog input signals and convert the samples to residue signals, perform the necessary processing on the residue signals, and convert the resultant residue signals back to analog output signals. Although techniques are readily available for efficiently converting analog/decimal or binary/digital signals to residue number signals, it is much more difficult to convert residue number signals back into analog signals. Since the RNS is not a weighted number system, its direct conversion to decimal/analog is not practical. One approach is to convert residue number signals to digital/binary signals and use one of the well known digital to analog conversion schemes to obtain the requisite analog/decimal signals.
Residue to analog conversion is described in the articles:
"Techniques for Residue-to-Analog Conversion for High Data Rate Digital Filtering" by W. K. Jenkins, 1978 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 804-807;
"An Efficient Residue-to-Decimal Converter" by F. J. Taylor and A. S. Ramnarayanan, IEEE Transactions on Circuits and Systems, Vol. 28, No. 12, December 1981, pages 1164-1169;
"An Improved Residue Number System Digital-to-Analog Converter" by M. A. Soderstrand, et al, IEEE Transactions on Circuits and Systems, Vol. 30, No. 12, December 1983, pages 903-907; and
"Techniques for Residue-to-Analog Conversion for Residue-Encoded Digital Filters" by W. K. Jenkins, IEEE Transactions on Circuits and Systems, Vol. 25, No. 7, July 1978, pages 555-562.
Prior art residue to binary/digital converters generally require considerable hardware and/or have relatively slow execution times and/or require considerable surface area, which is undesirable in an integrated circuit structure or implementation. Also, many of the prior art residue to analog converters require memories that store look-up tables and/or modulo adders, both of which are generally hardware intensive, slow in terms of overall execution time and/or are magnitude limited in that memory size dictates the maximum number of bits and thus the largest number that can be handled. The execution time of RNS to binary converters which require memory is normally dictated by the access time of the memory, (i.e., the time that it takes to obtain information from a memory location) which may be for CMOS ROMS in the order of 100 nanoseconds. Memory systems having much shorter execution times are very expensive and are even more magnitude limited (i.e., memories with short execution times normally have fewer bytes of memory). Stated differently, memories having larger storage capacity normally have longer execution times and require considerably more real estate, which is a disadvantage in an integrated circuit structure. This can be a significant limitation since the advantages of the RNS increase with the number of bits of memory that are available. By way of example, multiplication of 2 each n-bit numbers is n times faster in the RNS than in the binary number system without pipelining. Additionally, modulo adders are normally more complex than and require more surface area in integrated circuit implementations than do conventional binary adders.
An object of this invention is the provision of improved method and apparatus of performing modulo addition which is useful in method and apparatus for converting residue number signals to binary number signals.